package graph.weighted.shortestPath;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

import graph.weighted.CandyWeightedGraph;

/**
 * 
 * @Title: CandyBellmanFord.java 
 * @Package graph.weighted.shortestPath 
 * @Description: 使用BellmanFord算法求解最短路径问题
 * @author CandyWall   
 * @date 2021年1月21日 下午6:52:58 
 * @version V1.0
 */
public class CandyBellmanFord {
    private CandyWeightedGraph graph;
    private int s;
    private int[] distances;
    private boolean hasNegativeLoop;    // 是否包含负权环
    private int[] pres;
    
    public CandyBellmanFord(CandyWeightedGraph graph, int s) {
        this.graph = graph;
        graph.validateVertex(s);
        this.s = s;
        
        distances = new int[graph.getVertex_num()];
        pres = new int[graph.getVertex_num()];
        bellmanFord();
    }
    
    private void bellmanFord() {
        Arrays.fill(distances, Integer.MAX_VALUE);
        Arrays.fill(pres, -1);
        distances[s] = 0;
        // 进行graph.getVertext_num() - 1轮松弛操作
        for(int pass = 1; pass < graph.getVertex_num(); pass++) {
            // 遍历每一个顶点
            for(int v = 0; v < graph.getVertex_num(); v++) {
                // 找出和每一个顶点相邻的顶点
                for(int w : graph.adjacentVertexes(v)) {
                    if(distances[v] != Integer.MAX_VALUE 
                       && distances[v] + graph.getWeight(v, w) < distances[w]) {
                        distances[w] = distances[v] + graph.getWeight(v, w);
                        pres[w] = v;
                    }
                }
            }
        }
        
        // 再进行一次松弛度操作检测是否包含负权环
        for(int v = 0; v < graph.getVertex_num(); v++) {
            // 找出和每一个顶点相邻的顶点
            for(int w : graph.adjacentVertexes(v)) {
                if(distances[v] != Integer.MAX_VALUE 
                   && distances[v] + graph.getWeight(v, w) < distances[w]) {
                     hasNegativeLoop = true;
                }
            }
        }
    }
    
    public boolean hasNegativeLoop() {
        return hasNegativeLoop;
    }
    
    /**
     * 获取顶点s到顶点t的最短路径长度
     * @return
     */
    public int getShortestPathLength(int t) {
        graph.validateVertex(t);
        if(isConnectedTo(t)) {
            return distances[t];
        }
        return -1;
    }
    
    /**
     * 获取顶点s到顶点t的最短路径（具体经过了哪些边）
     * @return
     */
    public ArrayList<Integer> getShortestPath(int t) {
        graph.validateVertex(t);
        ArrayList<Integer> path = new ArrayList<>();
        if(!isConnectedTo(t)) {
            return path;
        }
        int cur = t;
        while(cur != s) {
            path.add(cur);
            cur = pres[cur];
        }
        path.add(s);
        Collections.reverse(path);
        return path;
    }

    private boolean isConnectedTo(int t) {
        graph.validateVertex(t);
        return distances[t] != Integer.MAX_VALUE;
    }

    public int[] getDistances() {
        return distances;
    }

    public static void main(String[] args) {
        CandyWeightedGraph graph1 = new CandyWeightedGraph("testData/weightedGraph/shortestPath/BellmanFord/graph1.txt");
        CandyBellmanFord bellmanFord1 = new CandyBellmanFord(graph1, 0);
        System.out.println(Arrays.toString(bellmanFord1.getDistances()));
        if(!bellmanFord1.hasNegativeLoop()) {
            System.out.println(bellmanFord1.getShortestPathLength(4));
            System.out.println(bellmanFord1.getShortestPath(4));
        } else {
            System.out.println("含有负权环");
        }
        System.out.println("=========================");
        CandyWeightedGraph graph2 = new CandyWeightedGraph("testData/weightedGraph/shortestPath/BellmanFord/graph3.txt", true);
        CandyBellmanFord bellmanFord2 = new CandyBellmanFord(graph2, 0);
        System.out.println(Arrays.toString(bellmanFord2.getDistances()));
        if(!bellmanFord2.hasNegativeLoop()) {
            System.out.println(bellmanFord2.getShortestPathLength(4));
            System.out.println(bellmanFord2.getShortestPath(4));
        } else {
            System.out.println("含有负权环");
        }
    }
}
